This application incorporates by reference Taiwanese application Ser. No. 88106873, Filed Apr. 4, 1999.
1. Field of the Invention
The invention relates in general to a table matching method for multiplication of elements in Galois Field, and more particularly to a method which can effectively obtain the product of elements in Galois Field by using a table formed in the computer hardware.
2. Description of the Related Art
Conventionally, binary scales are utilized to store and read data in a computer. An 8-bit byte is taken as an example. The byte xe2x80x9c00000000xe2x80x9d represents the value 0, the byte xe2x80x9c00000001xe2x80x9d represents the value 1, and similarly, the byte xe2x80x9c11111111xe2x80x9d represents the value 255. Herein, the symbol F{2{circumflex over ( )}8} is used to represent the 8-bit binary field. In the field F{2{circumflex over ( )}8}, every element represents a byte which corresponds to a value in [0,255] respectively. Moreover, the 8-bit Galois Field is denoted by GF{2{circumflex over ( )}8}. Every byte in the field GF{2{circumflex over ( )}8} can be represented by a value in {0, xcex1, xcex1{circumflex over ( )}2, . . . , xcex1{circumflex over ( )}255}, respectively, wherein xcex1 is xe2x80x9c00000010xe2x80x9d.
There are many well known methods or apparatuses taking use the characteristics of the Galois Field. For example, U.S. Pat. No. 5,694,407 deals with the calculation of error-detecting code in the intermediate network; and U.S. Pat. No. 4,994,995 discloses a method and apparatus for computing the result of the division of two finite elements in a Galois Field.
The multiplication operation, denoted by xe2x80x9c*xe2x80x9d of any byte A (b7,b6,b5,b4,b3,b2,b1,b0) in GF{2{circumflex over ( )}8} and xcex1 conventionally follows two steps. First, every bit bi (i=0xcx9c7) of the byte A should be first left-shifted for one bit. Then, according to the Equation (1), the product of A* xcex1 can be obtained.
A*xcex1=(b6,b5,b4,b3,b2,b1,bO, 0)⊕(0,0,0,b7,b7,b7,0,b7) xe2x80x83xe2x80x83(1) 
While any byte A (b7, b6, b5, b4,b3, b2, b1, b0) in GF{2{circumflex over ( )}8} is to be multiplied by xcex1, the multiplication, denoted by xe2x80x9c*xe2x80x9d is performed as follows: every bit bi (i=0xcx9c7) in the byte A should be first left-shifted for one bit, and then according to the Equation (1), the value of A* xcex1 can be obtained.
The operator xe2x80x9c⊕xe2x80x9d in the Equation (1) is an Exclusive OR (XOR) logic operator. The result of the above-mentioned multiplication can be obtained, basing on the equation xcex1{circumflex over ( )}8=xcex1{circumflex over ( )}4⊕xcex1{circumflex over ( )}3⊕xcex1{circumflex over ( )}2⊕xcex1{circumflex over ( )}0. Consequently, it is to be understood that xcex1{circumflex over ( )}2 is xe2x80x9c00000100xe2x80x9d, . . . , xcex1{circumflex over ( )}7 is xe2x80x9c10000000xe2x80x9d, and xcex1{circumflex over ( )}8 is xe2x80x9c00001101xe2x80x9d.
When the most significant bit (MSB), b7, of the byte A is xe2x80x9c1xe2x80x9d, according to the Equation (1), the value of A* xcex1 is the result of (b6,b5,b4,b3,b2,b1,b0,0) ⊕ (0,0,0,0,1,1,0,1). Thus, xcex1{circumflex over ( )}9 is xe2x80x9c00111010xe2x80x9d, . . . , xcex1{circumflex over ( )}12 is xe2x80x9c11001101xe2x80x9d, xcex1{circumflex over ( )}13 is xe2x80x9c10000111xe2x80x9d, . . . , and accordingly, xcex1{circumflex over ( )}255 is xe2x80x9c00000001xe2x80x9d. The operation including the steps of left shifting every bit for one bit and utilizing the XOR logic operation is called xe2x80x9cshift operation.xe2x80x9d
It is demonstrated that each of the 255 values, xcex1, xcex1{circumflex over ( )}2, . . . , xcex1{circumflex over ( )}255, corresponds to each byte in [1,255], respectively. The one-to-one relationship between the byte value A and the corresponding exponential number n (A=xcex1{circumflex over ( )}n) is shown in Table 1.
Conventionally, the multiplication product of the two elements A, B in GF{2{circumflex over ( )}8} is obtained by first expressing the multiplier B(Bxe2x89xa00) in the form of xcex1{circumflex over ( )}k (k=1xcx9c255). Time for finding the value k is assumed to be T. To obtain the product of A*B, the multiplicand A should be multiplied by xcex1 for k times and each time the shift operation mentioned above has to be performed once. Therefore, to multiply A by xcex1 for n times needs the shift operation to be applied for n times. This shift operation takes about one period T. While the value of k is large, such as 250, the shift operation has to be performed for 250 times, which takes at long as 250*T. Therefore, the time-consuming is highly increased.
It is therefore an object of the invention to provide a table matching method for the multiplication of elements in Galois Field. By utilizing a matching table of the byte values and the corresponding exponential numbers, the corresponding exponential numbers of the multiplicand and the multiplier are looked up respectively. Next, these two exponents are added up. Then, the corresponding byte value of the sum is look up from the table to quickly obtain the result of the multiplication.
In order to accomplish the object of the invention, a table matching method for the multiplication of elements in Galois Field is provided. The process includes at least the following steps. At first, a table between the byte value in [1,255] and the corresponding exponent in formed. These byte values 1xcx9c255 are set to be the addresses 1xcx9c255 in the computer hardware. Moreover, the corresponding exponents are stored in the hardware according to the addresses 1xcx9c255. Likewise, in the same table, the exponents 256xcx9c510 of the byte xcex1 are set to be the addresses 256xcx9c510, and their corresponding byte values xcex1=xcex1256,xcex12=xcex1257, . . . xcex1255=xcex1510 are stored in the addresses 256xcx9c510. When the multiplication operation between two elements in the Galois Field is operated, the corresponding exponents of the two elements are found out respectively. After the two exponents are added up, the corresponding byte value of the sum is obtained from the table. Therefore, the result of the multiplication can be obtained very quickly.